package exercises.leetcode;

import java.util.Random;

/**
 * <a href="https://leetcode-cn.com/problems/longest-palindromic-substring/">
 * 5. 最长回文子串</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * @author or2
 * @date 2021年10月12日 时间: 19:04
 */
public class No5 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0)
            return "";

        String str = manacherString(s);
        var palRadius = new int[str.length()];
        int C = -1, R = -1;
        int max = 0x8000_0000, index = -1;
        for (int i = 0, len = str.length(); i < len; i++) {

            palRadius[i] = R > i ? Math.min(palRadius[2 * C - i], R - i) : 1;

            while (i + palRadius[i] < len && i - palRadius[i] > -1 &&
                    str.charAt(i + palRadius[i]) == str.charAt(i - palRadius[i]))
                palRadius[i]++;

            if (i + palRadius[i] > R) {
                R = i + palRadius[i];
                C = i;
            }

            if (palRadius[i] > max) {
                max = palRadius[i];
                index = C;
            }
        }

        str = null;
        if (new Random().nextInt(30) == 1)
            System.gc();

        index = index - 1 >> 1;
        int oddEven = --max;
        max >>= 1;
        if ((oddEven & 1) == 1) {
            return s.substring(index - max, index + max + 1);
        } else
            return s.substring(index - max + 1, index + max + 1);
    }

    private String manacherString(String s) {
        int length = s.length();
        var res = new StringBuilder(length * 2 + 1);
        res.append('#');
        for (int i = 0; i < length; i++)
            res.append(s.charAt(i)).append('#');

        return res.toString();
    }
}
